The world financial crisis is quite a
subject. Some people are more relaxed while others are quite anxious. John is
one of them. He is very concerned about the evolution of the stock exchange. He
follows stock prices every day looking for rising trends. Given a sequence of
numbers p1, p2, ..., pn representing stock prices, a rising
trend is a subsequence pi1
< pi2 <
... < pik, with i1 < i2 < ... < ik.
John’s problem is to find very quickly the longest rising trend.
Input. Each data
set in the file stands for a particular set of stock prices. A data set starts
with the length l (l ≤ 100000) of the sequence of numbers, followed
by the numbers (a number fits a long integer).
White
spaces can occur freely in the input. The input data are correct and terminate
with an end of file.
Output. The
program prints the length of the longest rising trend.
For each
set of data the program prints the result to the standard output from the
beginning of a line.
|
Sample input |
Sample output |
|
6 5 2 1 4 5
3 3 1 1 1 4 4 3 2 1 |
3 1 1 |
наибольшая возрастающая
подпоследовательность
Состоит из
нескольких тестов. Каждый тест содержит последовательность чисел, для которой
следует найти длину наибольшей возрастающей подпоследовательности.
Реализация алгоритма
#include <cstdio>
#include <algorithm>
#define MAX 100001
using namespace
std;
int n, i, len, pos, element, lis[MAX];
int main(void)
{
while(scanf("%d",&n)
== 1)
{
for (len = i = 0; i < n; i++)
{
scanf("%d",&element);
pos = lower_bound(lis,lis+len,element)
- lis;
if (pos < len) lis[pos] = element; else lis[len++] = element;
}
printf("%d\n",len);
}
return 0;
}